package problem230_Kth_Smallest_Element_in_a_BST;

import problem105_Construct_Binary_Tree_from_Preorder_and_Inorder_Traversal.SolutionNonRecursive.TreeNode;

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
    	if(root==null) return -1;
    	int left=countSize(root.left);
    	if(left+1==k)
    		return root.val;
    	else if(left+1>k)
    		return kthSmallest(root.left, k);
    	else
    		return kthSmallest(root.right, k-left-1);
    }
    
    private int countSize(TreeNode node){
    	if(node==null)
    		return 0;
    	return 1+countSize(node.left)+countSize(node.right);
    }
}
